Gekr�mte Kurven sehen sch�ner aus als gerade Linien und Boxen. Doch sie sind nicht so einfach zu berechnen. B�zier-Kurven sind der gute Kompromi� zwischen Aufwand und Geschwindigkeit. Theorie und Praxis in C finden in diesem Artikel.
von Clemens Marschner
Ob bei Zeichens�tzen, Illustrationsprogrammen oder Bewegungspfaden f�r Kameras - B�zier-Kurven sind aus dem Computeralltag fast nicht mehr wegzudenken. Sie erlauben es, f�r skalierbare Zeichens�tze Kurven einzusetzen, ohne da� man eine Qualit�tseinbu�e bemerkt. Illustrationsprogramme arbeiten mit dieser Technik, um gekr�mmte Formen darzustellen. Und auch Raytracing- und CAD-Programme benutzen entweder B�ziers oder Splines, eine andere Art von Kurven. Leider hat man dem Amiga keine entsprechende Routine mit auf den Weg gegeben. Das soll hier nachgeholt werden.
Um gekr�mmte Kurven zu implementieren, ben�tigt man die mathematische Repr�sentation einer Kurve. Dazu ein anschauliches Beispiel:
Stellen Sie sich ein sehr biegsames, magnetisches Lineal vor. In seinem Grundzustand ist es eine Linie, die beiden Endpunkte des Lineals beschreiben genau die Position. Man nehme nun einen Magnet, um das Lineal in eine Richtung auszulenken. Das Resultat ist eine Kurve.
Dieses Beispiel ist aber nicht ganz korrekt, da ein Lineal seine L�nge nicht �ndert, Bezier-Kurven dagegen l�nger werden, je weiter der �Magnet� sich vom Lineal entfernt. Au�erdem nimmt der Einflu� eines Magneten mit seinem Abstand zum Lineal ab, bei B�zier-Kurven gilt das nicht.
Nat�rlich kann man auch mehrere Magneten, man spricht hier von Kontrollpunkten, verwenden. Bei zweien lassen sich eine Kurve, eine �Schlangenlinie�, eine Blase oder eine Schleife zaubern (s. Abbildung). Nimmt man noch mehr Kontrollpunkte, kann man fast jede beliebige Form erzeugen.
Doch dies ist meist nicht sinnvoll. Die Berechnungszeit steigt mit jedem Kontrollpunkt rapide an. Man beschr�nkt sich daher auf zwei End- und zwei Kontrollpunkte, um eine Kurve zu beschreiben, und setzt statt dessen mehrere B�zier-Kurven aneinander, um zu einem Objekt zu kommen.
Wie sieht das mathematisch aus? Der einfachste Algorithmus, der die Kurven beschreibt (nach seinem Erfinder Casteljau benannt), l��t sich am besten durch eine geometrische Konstruktion beschreiben (s. Bild �Casteljau�).
Die Eckdaten der Konstruktion bilden die Endpunkte der Kurve b0(0) und b3(0) sowie die St�tzpunkte b1(0) und b2(0). Diese werden reihum mit Vektoren verbunden. Der Trick an dem Algorithmus ist nun, da� man auf jedem der Vektoren, die die vier Punkte verbinden, gleichzeitig einen Punkt entlangwandern l��t. Wie in der Grafik zu sehen, werden diese Punkte wieder mit Vektoren verbunden. Auf diesen wandern wieder Punkte, die �ber Vektoren verbunden sind, bis zum Schlu� nur noch ein Vektor �brigbleibt, auf dem sich ein Punkt bewegt. Dieser malt die Bezierkurve. Er l��t bei seiner Wanderung quasi Farbe liegen.
Wichtig ist: Alle Punkte haben (prozentual) immer den gleichen Abstand zum Anfang- und Endpunkt ihrer Strecke. Sie teilen also die Strecke zum Anfang- und Endpunkt immer im gleichen Verh�ltnis auf. Dadurch wandert der Farbe liegenlassende Punkte vom Anfangs- zum Endpunkt der gesamten Kurve.
Die Kontrollpunkte (also End- und Ablenkungspunkte) sollen von b0(0) bis b3(0) durchnumeriert werden. Man verbindet alle Kontrollpunkte der Reihe nach mit Geradenst�cken. Dann l��t man eine Schleifenvariable t von 0 bis 1 laufen. Mit 0 steht man am Anfang eines Vektors, bei 1 ist der Endpunkt erreicht. Die Anzahl der Schritte zwischen 0 und 1 bestimmt die Genauigkeit, mit der die Kurve angen�hert wird. Eine Schrittweite von 1/60 zeichnet die Kurve also aus 60 Geradenst�cken. Der Erfahrung nach ist 60 f�r den Bildschirm v�llig ausreichend. Dennoch sollte man sich Gedanken machen, wie man aus den Koordinaten der Endpunkte die n�tige Schrittweite errechnet.
Man nimmt nun den Punkt, der eine Strecke im Verh�ltnis t zu 1-t teilt. (Im Bild haben sie den hochgestellten Index (1)). So verf�hrt man mit allen Strecken und verbindet sie wiederum der Reihe nach. Wenn man in diesem Schema fortf�hrt, kommt man auf den Punkt, der die Strecke b0(2) bis b1(2) teilt. Dieser Punkt ist Teil der Kurve.
Um die Kurve am Bildschirm zu zeichnen, m�ssen die errechneten Punkte nacheinander verbunden werden. Dabei ist der Punkt bei t=0 der Startpunkt und bei t=1 der Endpunkt, wie sich leicht nachvollziehen l��t.
Um dieses System als Computerprogramm schreiben zu k�nnen, ist die Kenntnis einiger elementarer geometrischer Grundbegriffe der Vektorrechnung n�tig. Eine kleine Einf�hrung bietet der Kasten �Vektorrechnung�.
Um rechnerisch auf den zu berechnenden Punkt zu kommen, gehen wir vom Startpunkt b0(0) aus. Seine Koordinaten k�nnen als Vektor vom Ursprung aus (als Punktvektor) aufgefa�t werden. Um auf b0(1) zu kommen, brauchen wir den Verbindungsvektor von b0(0) nach b1(0). Dieser ergibt sich, indem wir den Vektor von b0(0) umdrehen und b1(0) addieren.
Das Umdrehen geschieht durch Negation des Vektors:
u = -b0(0) + b1(0) bzw.
u = b1(0) - b0(0) (1)
u sei also der Verbindungsvektor. Um von u aus b0(1) zu erhalten, wird er mit t malgenommen. Sie k�nnen sich das leicht �berlegen: wenn t 0 ist, ist auch der Vektor von b0(0) nach b0(1) 0, das Resultat bleibt der Startpunkt. Bei t=1 ist der Punkt nach b1(0) gewandert.
Als Punkt b0(1) ergibt sich dann:
b0(1) = b0(0) + t*u
aus (1) folgt:
b0(1) = b0(0) + t * (b1(0) - b0(0))
zusammengefa�t:
b0(1) = (1 - t)*b0(0) + t*b1(0)
Genauso k�nnen wir mit den �brigen drei Strecken verfahren, wobei wir bei der zweiten Strecke statt von b0(0) von b1(0) ausgehen und den Vektor nach b2(0) berechnen. Beim ersten Durchgang sind also, von vier Punkten ausgehend, drei Berechnungen n�tig, die drei Punkte liefern. Diese lassen sich zu zwei Strecken verbinden, usw. Mit jedem Durchgang reduziert sich die Anzahl der Berechnungen also um eins.
Wir k�nnen also in einer �u�eren Schleife (r) von 4 abw�rts bis 1 z�hlen, und in einer inneren Schleife (i) von 0 bis 4-r. Zur Berechnung eines Punkts wird dabei immer das Ergebnis der vorherigen Rechnung, bzw. die Kontrollpunkte verwendet.
Die mathematisch korrekte Notation ist ein wenig komplizierter (n sei die Anzahl der Kontrollpunkte, in unserem Beispiel 4): Hier gilt f�r 1 <= r <= n, 0 <= i <= n-r:
bi(r) = (1-t)*bi(r-1)+t*bi+1(r-1)
bi(0) sind dabei die Kontrollpunkte. Die berechneten Zwischenpunkte bilden - wenn man sie �bereinander stellt - ein Dreieck:
b0(0)
b1(0) b0(1)
b2(0) b1(1) b0(2)
b3(0) b2(1) b1(2) b0(3)
Deshalb ist es zweckm��ig, f�r die Ablage der berechneten Werte eine 4x4-Matrix zu benutzen. Bei geschickter Programmierung l��t sich das Feld auf 1x5 reduzieren, doch wir werden das Programm an anderer Stelle optimieren.
So wie die Routine �Bezier1� im Listing zu sehen ist, l��t sie sich f�r jede beliebige Anzahl von St�tzpunkten verwenden. Man mu� nur die Matrix und die Anzahl der �bergebenen Parameter anpassen. Wie jedoch schon erw�hnt, werden meist nur zwei Ablenkpunkte gebraucht.
Um dieses Verfahren zu beschleunigen, wurden die inneren Schleifen aufgel�st und die entstehenden Gleichungen ineinander eingesetzt. Die resultierende Routine kommt ohne Matrix aus, sie operiert nur noch mit den Parametern. Auch Schleifen gibt es nur noch eine: die, um t von 0 bis 1 laufen zu lassen. Die entstandene Routine mu� deutlich weniger Additions- und Multiplikationsanweisungen durchf�hren. Eine weitere Steigerung bringt die vorherige Berechnung der Werte, die f�r x und y identisch sind.
Die resultierende Routine �Bezier3� ist hinsichtlich ihrer Geschwindigkeit gut optimiert. Auch Amiga-500-Besitzer k�nnen einzelne Kurven in flotter Geschwindigkeit zeichnen lassen. Auf der PD-Diskette zu dieser Ausgabe (bzw. der CD) sind zwei Beispielprogramme enthalten. Das eine bietet die M�glichkeit, ein bi�chen mit B�zier-Kurven am Bildschirm zu experimentieren (DrawBezier), das zweite baut, ausgehend von einem Datenfeld, den Buchstaben �P� in verschiedenen Gr��en am Bildschirm auf (PsZeichnen). Dazu wurden die Move- und Draw-Befehle durch AreaMove/AreaDraw ersetzt. Das Ergebnis ist zwar keine fotosatzf�hige Typographie, aber vielleicht eine Anregung, die B�zier-Routine in eigenen Programmen zu verwenden.
dg
Literatur:
[1] Thomas Rauber: Algorithmen in der Computergraphik; Teubner-Verlag; Stuttgart, 1993; ISBN 3-519-02127-7
[2] Bart u.a.: Anschauliche Analytische Geometrie; Ehrenwirth-Verlag; M�nchen, 1993; ISBN 3-431-03021-1
Vektoren sind eine raffinierte, einfache Methode, mathematisch geometrische Formen zu berechnen. Ein Vektor ist �die Menge aller gleichgerichteten, parallelen Pfeile�. Das hei�t, die Richtung und die L�nge bestimmen einen Vektor, nicht die Lage. Ein Vektor besteht also aus zwei bedeutsamen Angaben: Der Richtung (auch Winkel), in die er zeigt, und die L�nge (in einer praktischen Einheit). Diese Angaben sind quasi Koordinaten, wie sie auch ein Punkt in der Fl�che hat.
Um nun nicht mit trigonometrischen Funktionen wie Sinus und Cosinus hantieren zu m�ssen (f�r den Winkel oder die Richtung), beschreibt man einen Vektor mit Koordinaten - wie bei einem Punkt. Der Vektor ist dann die Strecke vom Nullpunkt des Koordinatensystems zum angegebenen Punkt.
Am einfachsten ist dies beim Zahlenstrahl: Er hat die Dimension 1, das hei�t, wir brauchen nur eine Koordinate, um jede Zahl beschreiben zu k�nnen. Die Addition zweier Zahlen l��t sich mit Hilfe der genannten Pfeile vornehmen (Fall 1). Um zum Beispiel die Vektoren mit der L�nge 5 und der L�nge 2 zu addieren, setzt man die Pfeile hintereinander, das hei�t das Ende des zweiten Pfeils an die Spitze des ersten. Das Ergebnis ist ein Vektor vom Ende des ersten Pfeils bis zur Spitze des zweiten. Er hat die L�nge 7.
Die Subtraktion funktioniert genauso. Sie entspricht einer Addition mit einer negativen Zahl, d.h. der Pfeil schaut jetzt nach links (Fall 2).
Um diese Operationen bei zweidimensionalen Vektoren auszuf�hren, m�ssen wir sie nur auf ihre einzelnen Komponenten anwenden, wie Fall 3 zeigt. Auch hier ist der resultierende Vektor der, der entsteht, wenn man den Fu� des zweiten Pfeils an die Spitze des ersten anh�ngt und dann den Vektor vom Fu� des ersten zur Spitze des zweiten betrachtet. Allerdings l��t sich die L�nge des resultierenden Vektors nicht mehr so einfach als Summe der L�ngen der Ursprungsvektoren berechnen. F�r eine Subtraktion mu� ein Pfeil nur umgedreht werden.
Man kann einen Vektor auch mit einer Zahl multiplizieren. Das hei�t nichts anderes, als da� alle Koordinatenangaben mit dieser Zahl multipliziert werden, man spricht hier von einer S-Multiplikation. Bei t*u
hei�t das: wenn t innerhalb von 0 und 1 ist, hat der resultierende Vektor die gleiche Richtung, ist aber k�rzer als zuvor. F�r t < 0 wird die Pfeilspitze umgedreht. -u entspricht also -1*u.
Diese Gesetze gelten ganz unabh�ngig davon, in welcher Dimension sich die Rechnung abspielt, sie sind also f�r den Zahlenstrahl (Dimension 1) genauso g�ltig wie f�r den uns bekannten Raum (Dimension 3).
� Copyright by MagnaMedia Verlag AG, Haar bei M�nchen
Ver�ffentlichung und Vervielf�ltigung nur mit schriftlicher Genehmigung des Verlags